class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

import collections
class Codec:
    def encode(self, root):
        """Encodes an n-ary tree to a binary tree.
        :type root: Node
        :rtype: TreeNode
        """
        if not root:
            return None
        stack = [root]
        out_root = TreeNode(root.val)
        state = 1
        out_stack = [out_root]
        while stack:
            next_stack = collections.deque()
            next_out_stack = collections.deque()
            for i in range(len(stack)):
                for item in stack[i].children:
                    next_stack.append(item)
                    node = TreeNode(item.val)
                    next_out_stack.append(node)
                    if state > 0:
                        out_stack[i].left = node
                        out_stack[i] = node
                    else:
                        out_stack[i].right = node
                        out_stack[i] = node
            stack = next_stack
            out_stack = next_out_stack
            state = - state
        return out_root


    def decode(self, data):
        """Decodes your binary tree to an n-ary tree.
        :type data: TreeNode
        :rtype: Node
        """
        if not data:
            return None
        state = 1
        out_root = Node(data.val, [])
        stack = [data]
        out_stack = [out_root]
        while stack:
            next_stack = collections.deque()
            next_out_stack = collections.deque()
            if state > 0:
                for i, item in enumerate(stack):
                    while item.left:
                        item = item.left
                        next_stack.append(item)
                        node = Node(item.val, [])
                        out_stack[i].children.append(node)
                        next_out_stack.append(node)
            else:
                for i, item in enumerate(stack):
                    while item.right:
                        item = item.right
                        next_stack.append(item)
                        node = Node(item.val, [])
                        out_stack[i].children.append(node)
                        next_out_stack.append(node)
            state = - state
            stack = next_stack
            out_stack = next_out_stack
        return out_root
